package class03;

import java.util.Stack;

public class Code05_GetMinStack {

	/**
	 * 实现一个特殊的栈结构，在基础栈功能之上，支持O(1)时间复杂度获取栈中最小元素
	 * 
	 * 设计思路：
	 * 使用两个栈：
	 * 1. 数据栈(stackData)：存储实际数据
	 * 2. 最小值栈(stackMin)：存储每一步的最小值
	 * 
	 * 核心优化：
	 * 通过空间换时间的策略，维护一个额外的最小值栈，使得获取最小值的操作时间复杂度为O(1)
	 */
	public static class MyStack1 {
		private Stack<Integer> stackData; // 数据栈，存储实际压入的元素
		private Stack<Integer> stackMin;  // 最小值栈，存储每一步的最小值

		/**
		 * 构造函数，初始化两个栈
		 */
		public MyStack1() {
			this.stackData = new Stack<Integer>();
			this.stackMin = new Stack<Integer>();
		}

		/**
		 * 向栈中压入新元素
		 * 时间复杂度：O(1)
		 * 空间复杂度：O(1) 均摊
		 * 
		 * @param newNum 要压入的整数
		 */
		public void push(int newNum) {
			// 数据栈总是需要压入新元素
			if (this.stackMin.isEmpty()) {
				// 如果最小值栈为空，说明是第一个元素，直接压入最小值栈
				this.stackMin.push(newNum);
			} else if (newNum <= this.getmin()) {
				// 如果新元素小于等于当前最小值，则更新最小值栈
				this.stackMin.push(newNum);
			}
			// 数据栈压入新元素
			this.stackData.push(newNum);
		}

		/**
		 * 弹出栈顶元素
		 * 时间复杂度：O(1)
		 * 
		 * @return 栈顶元素值
		 * @throws RuntimeException 当栈为空时抛出异常
		 */
		public int pop() {
			if (this.stackData.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			int value = this.stackData.pop(); // 弹出数据栈顶元素
			if (value == this.getmin()) {
				// 如果弹出的元素是当前最小值，则同步弹出最小值栈顶元素
				this.stackMin.pop();
			}
			return value;
		}

		/**
		 * 获取栈中最小元素
		 * 时间复杂度：O(1)
		 * 
		 * @return 当前栈中最小元素值
		 * @throws RuntimeException 当栈为空时抛出异常
		 */
		public int getmin() {
			if (this.stackMin.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			return this.stackMin.peek(); // 返回最小值栈的栈顶元素
		}
	}

	/**
	 * MyStack1的另一种实现方式
	 * 
	 * 设计思路：
	 * 同样使用两个栈，但在最小值栈中保存与数据栈相同数量的元素
	 * 每个位置保存的是到该位置为止的最小值
	 * 
	 * 特点：
	 * 1. 最小值栈与数据栈大小始终相同
	 * 2. 空间占用略高，但逻辑更简单
	 */
	public static class MyStack2 {
		private Stack<Integer> stackData; // 数据栈，存储实际压入的元素
		private Stack<Integer> stackMin;  // 最小值栈，存储每一步的最小值

		/**
		 * 构造函数，初始化两个栈
		 */
		public MyStack2() {
			this.stackData = new Stack<Integer>();
			this.stackMin = new Stack<Integer>();
		}

		/**
		 * 向栈中压入新元素
		 * 时间复杂度：O(1)
		 * 
		 * @param newNum 要压入的整数
		 */
		public void push(int newNum) {
			if (this.stackMin.isEmpty()) {
				// 如果最小值栈为空，说明是第一个元素，直接压入最小值栈
				this.stackMin.push(newNum);
			} else if (newNum < this.getmin()) {
				// 如果新元素小于当前最小值，则更新最小值栈
				this.stackMin.push(newNum);
			} else {
				// 如果新元素大于等于当前最小值，则重复压入当前最小值
				int newMin = this.stackMin.peek();
				this.stackMin.push(newMin);
			}
			// 数据栈压入新元素
			this.stackData.push(newNum);
		}

		/**
		 * 弹出栈顶元素
		 * 时间复杂度：O(1)
		 * 
		 * @return 栈顶元素值
		 * @throws RuntimeException 当栈为空时抛出异常
		 */
		public int pop() {
			if (this.stackData.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			// 由于两个栈大小相同，可以直接弹出最小值栈元素
			this.stackMin.pop();
			return this.stackData.pop(); // 返回数据栈顶元素
		}

		/**
		 * 获取栈中最小元素
		 * 时间复杂度：O(1)
		 * 
		 * @return 当前栈中最小元素值
		 * @throws RuntimeException 当栈为空时抛出异常
		 */
		public int getmin() {
			if (this.stackMin.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			return this.stackMin.peek(); // 返回最小值栈的栈顶元素
		}
	}

	public static void main(String[] args) {
		MyStack1 stack1 = new MyStack1();
		stack1.push(3);
		System.out.println(stack1.getmin());
		stack1.push(4);
		System.out.println(stack1.getmin());
		stack1.push(1);
		System.out.println(stack1.getmin());
		System.out.println(stack1.pop());
		System.out.println(stack1.getmin());

		System.out.println("=============");

		MyStack1 stack2 = new MyStack1();
		stack2.push(3);
		System.out.println(stack2.getmin());
		stack2.push(4);
		System.out.println(stack2.getmin());
		stack2.push(1);
		System.out.println(stack2.getmin());
		System.out.println(stack2.pop());
		System.out.println(stack2.getmin());
	}

}